from cmath import inf
from typing import List


class Solution:
    """
    方法：动态规划，从左上到右下计算最小路径和
    
    Args:
        grid: List[List[int]] - 给定的网格，每个位置包含非负整数
        
    Returns:
        int: 从左上角到右下角的最小路径和
        
    Time: O(m*n) - m和n分别为网格的行数和列数，需要遍历整个网格
    
    Space: O(m*n) - 使用二维dp数组存储中间结果
    """
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        f = [[inf] * (n + 1) for _ in range(m + 1)]
        f[0][1] = 0
        for i, row in enumerate(grid):
            for j, x in enumerate(row):
                f[i+1][j+1] = min(f[i+1][j], f[i][j+1]) + x
        return f[m][n]

    
    def minPathSum1(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        f = grid[0]
        for j in range(1, n):
            f[j] += f[j-1]
        for i in range(1, m):
            f[0] += grid[i][0]
            for j in range(1, n):
                f[j] = min(f[j-1], f[j]) + grid[i][j]
        return f[-1]